#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        int count = 0, m = 0, n = s.size();
//        vector<int> hash1(26);
//        vector<int> hash2(26);
//
//        for (auto ch : p)  hash2[ch - 'a']++;
//        m = p.size();
//        int left = 0, right = 0;
//        vector<int> ret;
//        while (right < n)
//        {
//            char in = s[right];
//            if (hash2[in - 'a'] > hash1[in - 'a'])
//            {
//                count++;
//            }
//            hash1[in - 'a']++;
//            if (right - left + 1 > m)
//            {
//                char out = hash1[left];
//                hash1[out - 'a']--;
//                if (count == m)
//                {
//                    ret.push_back(left);
//                }
//                left++;
//            }
//            right++;
//        }
//        return ret;
//
//
//
//    }
//};
//int main()
//{
//    auto ret=Solution().findAnagrams("cbaebabacd", "abc");
//    return 0;
//}
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int gap = words[0].size();
        int n = s.size();
        int m = words.size();
        vector<int> ret;
        unordered_map<string, int> hash1;
        unordered_map<string, int> hash2;
        for (auto& word : words)
            hash2[word]++;

        for (int i = 0; i < gap; i++)
        {
            int left = i, right = i;
            int count = 0;
            while (right < n)
            {
                string in = s.substr(right,  gap);

                if (hash1[in]++ < hash2[in])
                {
                    count++;
                }
                if (right - left + 1 > m*gap)
                {
                    string out = s.substr(left, left + gap);
                    if (--hash1[out] < hash2[out])
                    {
                        count--;
                    }
                    left += gap;
                }
                if (count == m)
                {
                    ret.push_back(left);
                }
                right += gap;
            }
        }
        return ret;


    }
};
int main()
{
    vector<string> tmp = { "foo", "bar" };
    auto ret = Solution().findSubstring("barfoothefoobarman", tmp);
    return 0;
}